package q_2_3;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import junit.framework.Assert;

import org.junit.Test;

public class Q_2_3 {
	public static class Node {
		public int value;
		public Node next;
	}
	
	public static Node add(Node a, Node b) {
		if(a == null || b == null) {return null;}
		Node head = null;
		Node tail = null;
		int inc = 0;
		while(a != null || b != null) {
			int num;
			if(a == null) {num = b.value + inc; b = b.next;}
			else if (b == null) { num = a.value + inc; a = a.next;}
			else {num = a.value + b.value + inc; a = a.next; b = b.next;}
			
			if(num >= 10) {
				num -= 10; inc = 1;
			} else {
				inc = 0;
			}
			
			Node n = new Node();
			n.value = num;
			if(head == null) {
				head = n;
				tail = head;
			} else {
				tail.next = n;
				tail = tail.next;
			}
		}
		if(inc == 1) {
			tail.next = new Node();
			tail.next.value = 1;
		}
		return head;
	}
	
	public static Node encode(List<Integer> list) {
		if(list == null) {
			return null;
		}
		Node tail = null;
		for(int i : list) {
			Node cur = new Node();
			cur.value = i;
			cur.next = tail;
			tail = cur;
		}
		return tail;
	}
	
	public static List<Integer> decode(Node head) {
		if(head == null) {return null;}
		LinkedList<Integer> list = new LinkedList<Integer>();
		while(head != null) {
			list.add(0, head.value);
			head = head.next;
		}
		return list;
	}
	
	public static boolean compare(List<Integer> a, List<Integer> b) {
		if(a == null && b == null) {
			return true;
		} else if (a == null || b == null) {
			return false;
		} else {
			return Arrays.deepEquals(a.toArray(new Integer[0]), b.toArray(new Integer[0]));
		}
	}
	
	public static boolean experiment(List<Integer> expect, List<Integer> a, List<Integer> b) {
		Node input1 = encode(a);
		Node input2 = encode(b);
		Node output = add(input1, input2);
		List<Integer> result = decode(output);
		return compare(expect, result);
	}
	
	@Test
	public void test() {
		Assert.assertTrue(experiment(null, null, null));
		Assert.assertTrue(experiment(null, Arrays.asList(0), null));
		Assert.assertTrue(experiment(null, null, Arrays.asList(0)));
		Assert.assertTrue(experiment(Arrays.asList(0), Arrays.asList(0), Arrays.asList(0)));
		Assert.assertTrue(experiment(Arrays.asList(1, 2), Arrays.asList(5), Arrays.asList(7)));
		Assert.assertTrue(experiment(Arrays.asList(1, 3, 2), Arrays.asList(3, 5), Arrays.asList(9, 7)));
		Assert.assertTrue(experiment(Arrays.asList(2, 1), Arrays.asList(1, 5), Arrays.asList(6)));
		Assert.assertTrue(experiment(Arrays.asList(2, 1), Arrays.asList(5), Arrays.asList(1, 6)));
	}
}
